package com.wtgroup.demo.leetcode.q005_最长回文子串;

public class S_DynamicProgramming {
    /*
    * 动态规划
    *
    * 参考 S_Force 思路, 很多小子串的 '是否回文串' 信息计算完就丢了, 没有'备忘',
    * 如果考虑用动态规划, 则可以复用这些信息. 从而 O(n3) --> O(n2).
    *
    * P(i,j) = P(i+1, j-1) && (Si==Sj)
    *
    * 起止坐标.
    * */

    public String longestPalindrome(String s) {
        if (s==null || s.length()==0) {
            return "";
        }

        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int m = 1; m <= n; m++) {
            for (int i = 0; i <= n-m; i++) {
                int j = i + m -1;
                if(m == 1) {
                    // 一个必是
                    dp[i][j] = true;
                } else if (m == 2) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                }
                if (dp[i][j] && m > ans.length()) {
                    // 就算遇到了更长的, 依然要继续下去, 这样备忘录才会是全的, 下次更长的才会有可用的结果.
                    ans = s.substring(i, i + m);
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        // String in = "babad";
        // String in = "cbbd";
        // String in = "a";
        // String in = "ac";
        String[] ss = {"babad", "cbbd", "a", "ac", "fgosujtgyeowsyhuermhldjhldrdlgjslgjfsaopyrtgujsdlhkjlsegjsl"};
        for (String s : ss) {
            System.out.println(new S_DynamicProgramming().longestPalindrome(s));
        }
    }
}
